package cxydmmszl.chapter01.t006;

import java.util.Stack;

/**
 * 用栈来求解汉诺塔问题
 *
 * @author habitplus
 * @since 2021-08-23 22:08
 */
public class Main {
    public int hanoiProblem2(int num, String left, String mid, String right) {
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> midStack = new Stack<>();
        Stack<Integer> rightStack = new Stack<>();
        leftStack.push(Integer.MAX_VALUE);
        midStack.push(Integer.MAX_VALUE);
        rightStack.push(Integer.MAX_VALUE);

        for (int i = num; i > 0; i--) {
            leftStack.push(i);
        }

        Action[] record = {Action.No};

        int step = 0;

        while (rightStack.size() != num + 1) {
            step += fStackTotStack(record, Action.MToL, Action.LToM, leftStack, midStack, left, mid);
            step += fStackTotStack(record, Action.LToM, Action.MToL, midStack, leftStack, mid, left);
            step += fStackTotStack(record, Action.RToM, Action.MToR, midStack, rightStack, mid, right);
            step += fStackTotStack(record, Action.MToR, Action.RToM, rightStack, midStack, right, mid);
        }

        return step;
    }

    private static int fStackTotStack(Action[] record, Action preNoAct, Action nowAct, Stack<Integer> fStack, Stack<Integer> tStack, String from, String to) {
        if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
            tStack.push(fStack.pop());
            System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
            record[0] = nowAct;
            return 1;
        }

        return 0;
    }

    public static void main(String[] args) {
        Main test = new Main();

        System.out.println(test.hanoiProblem2(5, "左柱子", "中柱子", "右柱子"));
    }
}

enum Action {
    No,     // 0 - 未定义
    LToM,   // 1 - 从左边移到中间
    MToL,   // 2 - 从中间移到左边
    MToR,   // 3 - 从中间移到右边
    RToM,   // 4 - 从右边移到中间
}
